package list

import "container/list"

// Problem Definition: https://leetcode.cn/problems/sliding-window-maximum/

func maxSlidingWindow(nums []int, k int) []int {
	if k == 1 {
		return nums
	}

	n := len(nums)
	ret := make([]int, n-k+1)
	dq := list.New()

	for i := 0; i < n; i++ {
		back := dq.Back()
		for back != nil && nums[back.Value.(int)] < nums[i] {
			dq.Remove(back)
			back = dq.Back()
		}

		dq.PushBack(i)

		if dq.Front().Value.(int)+k <= i {
			dq.Remove(dq.Front())
		}

		if i+1 >= k {
			ret[i-k+1] = nums[dq.Front().Value.(int)]
		}
	}

	return ret
}
